//class ListNode {
//    int val;
//    ListNode next;
//    ListNode() {}
//    ListNode(int val) { this.val = val; }
//    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//}

public class Solution2 {
    ListNode curN;
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        ListNode newHead =  new ListNode();
        curN = newHead;
        merge(cur1, cur2);
        return newHead.next;
    }
    private void merge(ListNode cur1, ListNode cur2) {
        if(cur1 == null) {
            curN.next = cur2;
            return;
        }
        if(cur2 == null){
            curN.next = cur1;
            return;
        }
        int val1 = cur1.val;
        int val2 = cur2.val;
        if(val1 < val2) {
            curN.next = cur1;
            curN = curN.next;
            merge(cur1.next, cur2);
        }else {
            curN.next = cur2;
            curN = curN.next;
            merge(cur1, cur2.next);
        }
    }
}